package com.squirrel.michale;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/30 7:09 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1792 {



    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> heap = new PriorityQueue<>((a, b) -> {
            double x = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            double y = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            return Double.compare(y, x);
        });
        for (int[] classInfo : classes) {
            heap.offer(new double[] {classInfo[0], classInfo[1]});
        }
        while (extraStudents-- > 0) {
            var classInfo = heap.poll();
            double pass = classInfo[0] + 1, total = classInfo[1] + 1;
            heap.offer(new double[] {pass, total});
        }
        double result = 0;
        while (!heap.isEmpty()) {
            var classInfo = heap.poll();
            result += classInfo[0] / classInfo[1];
        }
        return result / classes.length;
    }

//    作者：ylb
//    链接：https://leetcode.cn/problems/maximum-average-pass-ratio/solutions/2119717/python3javacgo-yi-ti-yi-jie-you-xian-dui-qrmo/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    public double maxAverageRatio2(int[][] classes, int extraStudents) {

        int classNumber = classes.length;
        double ratio = 0d;

        PriorityQueue<double[]> heap = new PriorityQueue<>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                return o2[0]-o1[0]>0?1:0;
            }
        });

        for (int i = 0; i < classNumber; i++) {
            int[] classInfo = classes[i];
            double passStudent = classInfo[0];
            double totalStudent = classInfo[1];
            double deltaRatio = (passStudent + 1) / (totalStudent + 1) - passStudent / totalStudent;
            double[] classAverageInfo = new double[]{deltaRatio,passStudent, totalStudent,i};
            heap.offer(classAverageInfo);
        }

        for (int i = 0; i < extraStudents; i++) {
            if (!heap.isEmpty()) {
                double[] poll = heap.poll();
                double passStudent = poll[1];
                double totalStudent = poll[2];
                double deltaRatio = (passStudent + 1) / (totalStudent + 1) - passStudent / totalStudent;
                double[] pollNew = new double[]{deltaRatio, passStudent + 1, totalStudent + 1, poll[3]};
                heap.offer(pollNew);
            }
        }






        return ratio / classNumber;

    }



}
